package com.dhnsoft.代码随想录.链表;

/**
 * ClassName: d06_02_链表相交
 * Package: com.dhnsoft.代码随想录.链表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/11 10:46
 * @Version 1.0
 */
public class d06_02_链表相交 {

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        if(headA==headB){
            return headA;
        }
        ListNode newNodeA = new ListNode(-1);
        ListNode newNodeB = new ListNode(-1);
        newNodeA.next = headA;
        newNodeB.next = headB;
        int lenA = 0;
        int lenB = 0;
        ListNode tempA = newNodeA.next;
        ListNode tempB = newNodeB.next;
        while (tempA!=null){
            lenA++;
            tempA = tempA.next;
        }
        while (tempB!=null){
            lenB++;
            tempB = tempB.next;
        }
        tempA = newNodeA.next;
        tempB = newNodeB.next;
        if(lenA>lenB){
            for (int i=0;i<lenA-lenB;i++){
                tempA = tempA.next;
            }
        }
        else{
            for (int i=0;i<lenB-lenA;i++){
                tempB = tempB.next;
            }
        }
        while (tempA!=null){
            if(tempA==tempB){
                return tempA;
            }
            tempA = tempA.next;
            tempB = tempB.next;

        }
        return null;
    }

    public static void main(String[] args) {
        LinkedNode singLinked = new LinkedNode();
        ListNode l1 = new ListNode(4);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(8);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        singLinked.add(l1);
        singLinked.add(l2);
        singLinked.add(l3);
        singLinked.add(l4);
        singLinked.add(l5);

        LinkedNode singLinked2 = new LinkedNode();
        ListNode ll1 = new ListNode(5);
        ListNode ll2 = new ListNode(0);
        ListNode ll3 = new ListNode(1);
        ListNode ll4 = new ListNode(8);
        ListNode ll5 = new ListNode(4);
        ListNode ll6 = new ListNode(5);
        singLinked2.add(ll1);
        singLinked2.add(ll2);
        singLinked2.add(ll3);
        singLinked2.add(ll4);
        singLinked2.add(ll5);
        singLinked2.add(ll6);

        ListNode intersectionNode = getIntersectionNode(singLinked.getHead(), singLinked2.getHead());
        System.out.println(intersectionNode);
    }
}
